package com.zofer.study.array;

/**
 * 题目：给定一个数组arr，返回子数组的最大累加和
 */
public class MaxSumOfSubArray {

    /**
     *【思路】用变量记录cur记录每一步的累加和，遍历到正数cur增加，遍历到负数cur减少。
     * 当cur<0时，说明累加到当前数出现了小于0的结果，那么累加的这一部分肯定不能
     * 作为产生最大累加和的子数组的左边部分，此时令cur = 0.表示从下一个数开始累加。
     * 当cur>=0，每一次累加都可能是最大的累加和。用max跟踪记录cur出现的最大值。
     * cur累加成为负数就清零重新累加，max记录cur的最大值即可。
     */
    public int maxsumofSubarray (int[] array) {
        // write code here
        if(array == null || array.length == 0){
            return 0;
        }

        int sum = 0;
        int max = 0;
        int fuNum = 0;
        int mostFuNum = 0;
        for(int i = 0;i < array.length;i++){
            //如果都是负数 begin
            if(array[i] < 0){
                fuNum++;
                if(mostFuNum == 0){
                    mostFuNum = array[i];
                }else if(mostFuNum < array[i]){
                    mostFuNum =  array[i];
                }
            }
            //如果都是负数 end
            sum = Math.max(array[i],sum + array[i]);
            max = Math.max(sum,max);
            sum = sum < 0? 0 : sum;
        }

        //如果都是负数
        if(fuNum == array.length){
            max = mostFuNum;
        }
        return max;
    }
}
